// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/

// 算法思路总结：
// 1. 使用状态机动态规划处理股票买卖问题
// 2. 三个状态：持有股票、刚卖出股票、冷却期
// 3. 状态转移考虑买卖和冷却限制
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int maxProfit(vector<int>& prices) 
    {
        int m = prices.size();
        if (m == 0) return 0;
        if (m == 1) return 0;

        int prev0 = -prices[0], prev1 = 0, prev2 = 0;
        int cur0, cur1, cur2;
        for (int i = 1 ; i < m ; i++)
        {
            cur0 = max(prev0, prev2 - prices[i]);
            cur1 = prev0 + prices[i];
            cur2 = max(prev1, prev2);

            prev0 = cur0;
            prev1 = cur1;
            prev2 = cur2;
        }
        return max(cur1, cur2);
    }
};

int main()
{
    vector<int> v1 = {1,2,3,0,2}, v2 = {1};
    Solution sol;

    cout << sol.maxProfit(v1) << endl;
    cout << sol.maxProfit(v2) << endl;

    return 0;
}